HW#1 --- last modified February 07 2019 04:44:12..

Solution set.

Due date: Feb 13

Files to be submitted:
  Hw1.zip

Purpose: To gain familiarity with the set notations and proofs that will be needed for this course. To get familiar with the definition of a formal language. To build our first finite automata.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

(2) Construct deterministic and non-deterministic machines for various languages.

Specification:You need a MathML compatible browser to view this page. The handwritten problems for this homework are grouped into groups of four. From each group two will be selected and graded. In class, we will go over these two problems in detail.

Group 1 (Must be handwritten, due start of class Jan 30).

1. Let `A = {1, 4, 5, 9}` and `B = {3, 4, 9}`. Write out fully the elements in each of the following sets (a) `A \cap B` (b) `B - A` (c) `S(A)` (d) `2^B` (e) `A times B`. Give the cardinality of each set.
2. Write down all possible partitions of the set `{1,2,3,4}`.
3. Show using only the properties (a)-(d) of this slide that `S^3(0) cdot S^6(0) = S^{18}(0)`.
4. Construct using `^^`, `vv`, `not` gates a boolean function `{0, 1}^4 rightarrow {0, 1}` which returns `1` if and only if at least half of the boolean inputs are `1`.

Group 2 (Must be handwritten, due start of class Feb 6).

1. Prove by induction that, `sum_(i=0)^n (3i^(2) +3i +1) = (n+1)^3`. Show carefully that this sum is `Theta(n^3)`.
2. Using the pigeonhole principle, show that every undirected graph without loops with two or more nodes contains two nodes that have equal to degree.
3. Draw a finite automata that accepts all string over `{0, 1}` that have an even number of `1`'s.
4. Write down the automata of the previous problem formally as a 5-tuple.

Group 3 (Must be handwritten, due start of class Feb 13).

1. Exercise 1.6 from the book.
2. Exercise 1.7 from the book.
3. Apply the Cartesian product construction to (i) and (j) of exercise 1.6 to obtain an automata recognizing the union of their languages.
4. Consider the variant of Exercise 1.38 where rather than being in the language occurs if every possible state that `M` could be in after reading input `x` is accepting, we instead only require more than half of the states be accepting. Prove that the resulting class also recognizes exactly the regular languages.

The non-handwritten portion of this homework consists in doing a little library archeology and in doing some JFLAP experiments.

First, I would like you two obtain the following two papers by physically going to our library, finding them, and scanning them using the scanning technique of your choice:

• W. S. McCulloch and W.H. Pitts. A logical calculus of the ideas immanent in nervous activity. Bulletin of Mathematical Biophysics. Volume 5. pp. 115--133. 1943.
• M. O. Rabin and D. Scott. Finite automata and their decision problems. IBM Journal of Research and Development. Volume 3. pp. 114--125. 1959.

Within the Hw1.zip file you submit for this homework have a Hw1.pdf file. In it, for each article, write a paragraph or two summary of what the authors' motivations were for their paper. Then answer the following questions:

1. McCulloch and Pitts is often cited as the first paper related to finite automata. How does their system compare with the DFAs as presented in class?
2. What results in the Rabin and Scott paper correspond to results we have presented in class so far?

For the JFLAP portion of the assignment, implement the automata for 1.7f in JFLAP. (Notice the letter A on the problem in the book -- Feb 12 take that solution add a redundant epsilon and 1 transition and see what happens to them after the construction). Save this file as NFA.jff and include it your Hw1.zip file. Next add screenshots to Hw1.pdf showing you in JFLAP stepping through the computation of this automata on the inputs 001, and 1001. Finally, add some more screenshots showing you stepping through the process of converting this NFA to a DFA.

Point Breakdown